[Previous] [Next] [Index] [Thread]

Re: Netscape Commerce Server and Certificates

-----BEGIN PGP SIGNED MESSAGE-----

At 6:24 9/23/95, Peter Trei wrote:

>Even if your 5 second/test estimate is correct (and I suspect the code
>could be substantially optimized),

5 seconds/test, nope.

Here is the first optimization:

The majority of the time required to generate an RSA key pair is the time
spent searching for the first prime given a random starting point. However
for primes in the 256-512 bit range, you will tend to find a prime within
100 or so numbers. So the only difference between the starting random
number and the located prime will be in the low order 7 to 8 bits on
average. Now you need two primes which are multiplied together. The result
of this multiplication, the public modulus, will have the same high order
bits (I believe for about half its length) as the product of the two random
starting points.

This means that to search for your private key, I only need to generate the
two candidate random starting points, multiply them together and compare
the high order bits (say 16 or 20 bits) of the result with the public
modulus of your key. If I find one that is a close match, I can then search
for the primes themselves (starting at the successful candidate starting
points) to verify if I have truly been successful.

This is not a hypothetical discussion, I have done this in practice and
have penetrated a product (beta test) this way.

RSA Key pairs (or any keys for that matter) that will have a long life (say
measured in months or years) *have* to be generated from significant
entropy.

                                -Jeff


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMGSbOcUtR20Nv5BtAQGvXAP9GLn5OMhcayS4i0RIfqE3xHQjun/6LWhW
fur0wIDhwVAIHelyP69bEyHPIzs9bgFepr1pSQrzRpqJT39+GbgX9vwSsZDh5lcR
dM9aqo5/tqbfz354NNLLEirWog0gZvim85g+QhlgWQhD8f4BKf8B0ltiKRsA3zpn
Z9jn/ne3Gzc=
=qSc+
-----END PGP SIGNATURE-----